package main

import (
	"fmt"
)

func heapSort(arr []int) {
	length := len(arr)

	for i := 0; i < length; i++ {

		lastmesslen := length - i //每次截取一段

		findHeapMax(arr, lastmesslen)

		//findMax(arr, lastmesslen)

		fmt.Println("sort:", arr)

		if lastmesslen > 1 {
			arr[0], arr[lastmesslen-1] = arr[lastmesslen-1], arr[0]
		}
		fmt.Println("op:", arr)

	}
}

//选择   排序的 第一值为最大值
func findMax(arr []int, length int) []int {

	if length <= 1 {
		return arr //一个元素直接返回
	} else {
		//有点像选择排序
		max := arr[0]
		maxIndex := 0
		for i := 1; i < length; i++ {
			if max < arr[i] {
				maxIndex = i
				max = arr[maxIndex]
			}
		}
		if maxIndex != 0 {
			arr[0], arr[maxIndex] = arr[maxIndex], arr[0]
		}
		//depth := length/2 + 1 // 深度
	}
	//fmt.Println(arr)
	return arr
}

// 堆排序  将最大值放到 // 二叉树最大树根
func findHeapMax(arr []int, length int) []int {
	if length <= 1 {
		return arr //一个元素直接返回
	} else {
		deepth := length/2 - 1 // 有子节点的节点数
		// fmt.Println(deepth)
		for i := deepth; i >= 0; i-- {
			maxIndex := i        //子节点的跟节点
			leftNode := i*2 + 1  //左节点
			rightNode := i*2 + 2 // 右节点

			//先让根节点和左节点比较
			if leftNode <= length-1 && arr[leftNode] > arr[maxIndex] {
				maxIndex = leftNode
			}

			//右节点和上面比较的比较,节点不能超出数组下标
			if rightNode <= length-1 && arr[rightNode] > arr[maxIndex] {
				maxIndex = rightNode
			}

			if maxIndex != i {
				arr[maxIndex], arr[i] = arr[i], arr[maxIndex]
			}

		}

		return arr
	}
}

func main() {
	arr := []int{3, 5, 4, 2, 9, 6, 78, 13, 9, 18, 16, 28, 22}
	// findHeapMax(arr, len(arr))

	heapSort(arr)

}

/**
sort: [78 18 3 13 5 28 4 2 9 9 16 6 22]
op: [22 18 3 13 5 28 4 2 9 9 16 6 78]
sort: [28 18 22 13 16 3 4 2 9 9 5 6 78]
op: [6 18 22 13 16 3 4 2 9 9 5 28 78]
sort: [22 18 6 13 16 3 4 2 9 9 5 28 78]
op: [5 18 6 13 16 3 4 2 9 9 22 28 78]
sort: [18 5 6 13 16 3 4 2 9 9 22 28 78]
op: [9 5 6 13 16 3 4 2 9 18 22 28 78]
sort: [16 9 6 13 5 3 4 2 9 18 22 28 78]
op: [9 9 6 13 5 3 4 2 16 18 22 28 78]
sort: [13 9 6 9 5 3 4 2 16 18 22 28 78]
op: [2 9 6 9 5 3 4 13 16 18 22 28 78]
sort: [9 2 6 9 5 3 4 13 16 18 22 28 78]
op: [4 2 6 9 5 3 9 13 16 18 22 28 78]
sort: [9 4 6 2 5 3 9 13 16 18 22 28 78]
op: [3 4 6 2 5 9 9 13 16 18 22 28 78]
sort: [6 5 3 2 4 9 9 13 16 18 22 28 78]
op: [4 5 3 2 6 9 9 13 16 18 22 28 78]
sort: [5 4 3 2 6 9 9 13 16 18 22 28 78]
op: [2 4 3 5 6 9 9 13 16 18 22 28 78]
sort: [4 2 3 5 6 9 9 13 16 18 22 28 78]
op: [3 2 4 5 6 9 9 13 16 18 22 28 78]
sort: [3 2 4 5 6 9 9 13 16 18 22 28 78]
op: [2 3 4 5 6 9 9 13 16 18 22 28 78]
sort: [2 3 4 5 6 9 9 13 16 18 22 28 78]
op: [2 3 4 5 6 9 9 13 16 18 22 28 78]


*/
